#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <omp.h>
#include <stdio.h>
#include "Knapsacks.h"

//reference: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

using namespace std;
//using namespace boost;

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

/* A Naive recursive implementation of 0-1 Knapsack problem */
// Return the maximum value that can be put in a knapsack of capacity W
int knapSackNaive(int W, int wt[], int val[], int n)
{
    // Base Case
    if (n==0||W==0)
        return 0;

    // If weight of the nth item is more than Knapsack capacity W,
    // then this nth item cannot be included in the optimal solution
    if (wt[n-1] > W)
        return knapSack(W,wt,val,n-1);

    // Return the maximum of two cases:
    // 1) nth item included, 2) not included
    else return max(val[n-1] + knapSack(W-wt[n-1],wt,val,n-1),
                    knapSack(W,wt,val,n-1));
}


// A Dynamic Programming based solution for 0-1 Knapsack problem
// Return the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    // build temporary array K[][] in bottom up manner
    // to avoid recomputations of same subproblems
    int K[n+1][W+1];
    for (i = 0; i<=n; i++)
    {
        for (w=0;w<=W;w++)
        {
            if (i==0||w==0)
                K[i][w]=0;
            else if (wt[i-1]<=w)
                K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],
                            K[i-1][w]);
            else
                K[i][w] = K[i-1][w];
        }
    }

    return K[n][W];
}




void Test_knapsack()
{

    int val[] = {60, 100, 120};
       int wt[] = {10, 20, 30};
       int  W = 50;
       int n = sizeof(val)/sizeof(val[0]);
       cout << knapSack(W, wt, val, n);


}
